SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Hadamard code</title>

</head>

Hadamard code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Hadamard code</th></tr><tr><th scope="row" class="infobox-label">Named after</th><td class="infobox-data"><a href="Jacques_Hadamard" title="Jacques Hadamard">Jacques Hadamard</a></td></tr><tr><th colspan="2" class="infobox-header" style="background:#ccf;">Classification</th></tr><tr><th scope="row" class="infobox-label">Type</th><td class="infobox-data"><a href="Linear_code" title="Linear code">Linear</a> <a href="Block_code" title="Block code">block code</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_block_length_n" title="Block code">Block length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k}}</annotation>

</semantics>

</math><img src="./a8242689a132230c6c847ae901f6f32dba8181ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.744ex; height:2.676ex;" alt="{\displaystyle n=2^{k}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_message_length_k" title="Block code">Message length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_rate_R" title="Block code">Rate</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k/2^{k}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k/2^{k}}</annotation>

</semantics>

</math><img src="./bc1f128115ee684a3b67b7eae86de374df25791d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.625ex; height:3.176ex;" alt="{\displaystyle k/2^{k}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_distance_d" title="Block code">Distance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2^{k-1}}</annotation>

</semantics>

</math><img src="./fa32888753dcde39eec03916502f82e85710067b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.666ex; height:2.676ex;" alt="{\displaystyle d=2^{k-1}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_alphabet_Σ" title="Block code">Alphabet size</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#Popular_notation" title="Block code">Notation</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{k},k,2^{k-1}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{k},k,2^{k-1}]_{2}}</annotation>

</semantics>

</math><img src="./4c61084e4ec593311b8d2e834afabf4d432a1916.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.23ex; height:3.176ex;" alt="{\displaystyle [2^{k},k,2^{k-1}]_{2}}" loading="lazy">-code</td></tr><tr><td colspan="2" class="infobox-navbar"><style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Augmented Hadamard code</th></tr><tr><th scope="row" class="infobox-label">Named after</th><td class="infobox-data"><a href="Jacques_Hadamard" title="Jacques Hadamard">Jacques Hadamard</a></td></tr><tr><th colspan="2" class="infobox-header" style="background:#ccf;">Classification</th></tr><tr><th scope="row" class="infobox-label">Type</th><td class="infobox-data"><a href="Linear_code" title="Linear code">Linear</a> <a href="Block_code" title="Block code">block code</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_block_length_n" title="Block code">Block length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k}}</annotation>

</semantics>

</math><img src="./a8242689a132230c6c847ae901f6f32dba8181ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.744ex; height:2.676ex;" alt="{\displaystyle n=2^{k}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_message_length_k" title="Block code">Message length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k+1}</annotation>

</semantics>

</math><img src="./552a558062ed4c0486297b5b5531c5ee044dbd9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k+1}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_rate_R" title="Block code">Rate</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k+1)/2^{k}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (k+1)/2^{k}}</annotation>

</semantics>

</math><img src="./3f06fbd2a3219b789687ec55abfd0931ad9a80a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.437ex; height:3.176ex;" alt="{\displaystyle (k+1)/2^{k}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_distance_d" title="Block code">Distance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2^{k-1}}</annotation>

</semantics>

</math><img src="./fa32888753dcde39eec03916502f82e85710067b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.666ex; height:2.676ex;" alt="{\displaystyle d=2^{k-1}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_alphabet_Σ" title="Block code">Alphabet size</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#Popular_notation" title="Block code">Notation</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}</annotation>

</semantics>

</math><img src="./33dd8f1c5efa897cd15747ab8be5b594038db3af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.233ex; height:3.176ex;" alt="{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}" loading="lazy">-code</td></tr><tr><td colspan="2" class="infobox-navbar"></td></tr></tbody></table>

The Hadamard code is an <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting code</a> named after the French mathematician <a href="Jacques_Hadamard" title="Jacques Hadamard">Jacques Hadamard</a> that is used for <a href="Error_detection_and_correction" title="Error detection and correction">error detection and correction</a> when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mars back to Earth from the NASA space probe <a href="Mariner_9" title="Mariner 9">Mariner 9</a>.<a href="#cite_note-Malek_2006-1">[1]</a> Because of its unique mathematical properties, the Hadamard code is not only used by engineers, but also intensely studied in <a href="Coding_theory" title="Coding theory">coding theory</a>, <a href="Mathematics" title="Mathematics">mathematics</a>, and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>.

The Hadamard code is also known under the names Walsh code, Walsh family,<a href="#cite_note-Amadei-Manzoli-Merani_2002-2">[2]</a> and Walsh–Hadamard code<a href="#cite_note-Arora-Barak_2009-3">[3]</a> in recognition of the American mathematician <a href="Joseph_Leonard_Walsh" class="mw-redirect" title="Joseph Leonard Walsh">Joseph Leonard Walsh</a>.

The Hadamard code is an example of a <a href="Linear_code" title="Linear code">linear code</a> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m}}</annotation>

</semantics>

</math><img src="./667d0154f26e56e3f7979803f08afac16b4dcb16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.837ex; height:2.343ex;" alt="{\displaystyle 2^{m}}" loading="lazy"> over a <a href="Binary_set" class="mw-redirect" title="Binary set">binary alphabet</a>.

Unfortunately, this term is somewhat ambiguous as some references assume a message length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=m}</annotation>

</semantics>

</math><img src="./81b1071d97e4f1ae74d676a06d0d896a9e06b9f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.35ex; height:2.176ex;" alt="{\displaystyle k=m}" loading="lazy"> while others assume a message length of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=m+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=m+1}</annotation>

</semantics>

</math><img src="./d5585d832b475721eb1fbb2fd412041245dc6d6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.353ex; height:2.343ex;" alt="{\displaystyle k=m+1}" loading="lazy">.

In this article, the first case is called the Hadamard code while the second is called the augmented Hadamard code.

The Hadamard code is unique in that each non-zero codeword has a <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> of exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}}</annotation>

</semantics>

</math><img src="./ddfa44836396d742f76f25213117e820c4584d2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.352ex; height:2.676ex;" alt="{\displaystyle 2^{k-1}}" loading="lazy">, which implies that the <a href="Block_code#The_distance_d" title="Block code">distance</a> of the code is also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}}</annotation>

</semantics>

</math><img src="./ddfa44836396d742f76f25213117e820c4584d2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.352ex; height:2.676ex;" alt="{\displaystyle 2^{k-1}}" loading="lazy">.

In standard <a href="Block_code#Popular_notation" title="Block code">coding theory notation</a> for <a href="Block_code" title="Block code">block codes</a>, the Hadamard code is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{k},k,2^{k-1}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{k},k,2^{k-1}]_{2}}</annotation>

</semantics>

</math><img src="./4c61084e4ec593311b8d2e834afabf4d432a1916.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.23ex; height:3.176ex;" alt="{\displaystyle [2^{k},k,2^{k-1}]_{2}}" loading="lazy">-code, that is, it is a <a href="Linear_code" title="Linear code">linear code</a> over a <a href="Binary_set" class="mw-redirect" title="Binary set">binary alphabet</a>, has <a href="Block_code#The_block_length_n" title="Block code">block length</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>

</semantics>

</math><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy">, <a href="Block_code#The_message_length_k" title="Block code">message length</a> (or dimension) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, and <a href="Block_code#The_distance_d" title="Block code">minimum distance</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}/2}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}/2}</annotation>

</semantics>

</math><img src="./284e806c2be54f50ae6253e27c969905a3fd87c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.576ex; height:3.176ex;" alt="{\displaystyle 2^{k}/2}" loading="lazy">.

The block length is very large compared to the message length, but on the other hand, errors can be corrected even in extremely noisy conditions.

The augmented Hadamard code is a slightly improved version of the Hadamard code; it is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}</annotation>

</semantics>

</math><img src="./33dd8f1c5efa897cd15747ab8be5b594038db3af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.233ex; height:3.176ex;" alt="{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}" loading="lazy">-code and thus has a slightly better <a href="Block_code#The_rate_R" title="Block code">rate</a> while maintaining the relative distance of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">, and is thus preferred in practical applications.

In communication theory, this is simply called the Hadamard code and it is the same as the first order <a href="Reed%E2%80%93Muller_code" title="Reed–Muller code">Reed–Muller code</a> over the binary alphabet.<a href="#cite_note-Guruswami_2009-4">[4]</a>

Normally, Hadamard codes are based on <a href="Hadamard_matrix#Sylvester's_construction" title="Hadamard matrix">Sylvester's construction of Hadamard matrices</a>, but the term “Hadamard code” is also used to refer to codes constructed from arbitrary <a href="Hadamard_matrix" title="Hadamard matrix">Hadamard matrices</a>, which are not necessarily of Sylvester type.

In general, such a code is not linear.

Such codes were first constructed by <a href="Raj_Chandra_Bose" title="Raj Chandra Bose">Raj Chandra Bose</a> and <a href="Sharadchandra_Shankar_Shrikhande" title="Sharadchandra Shankar Shrikhande">Sharadchandra Shankar Shrikhande</a> in 1959.<a href="#cite_note-Bose-Shrikhande_1959-5">[5]</a>

If n is the size of the Hadamard matrix, the code has parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,2n,n/2)_{2}}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,2n,n/2)_{2}}</annotation>

</semantics>

</math><img src="./5a277e77cddb7e42e5faf40fafeb64b5eaf560f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.603ex; height:2.843ex;" alt="{\displaystyle (n,2n,n/2)_{2}}" loading="lazy">, meaning it is a not-necessarily-linear binary code with 2n codewords of block length n and minimal distance n/2. The construction and decoding scheme described below apply for general n, but the property of linearity and the identification with Reed–Muller codes require that n be a power of 2 and that the Hadamard matrix be equivalent to the matrix constructed by Sylvester's method.

The Hadamard code is a <a href="Locally_decodable" class="mw-redirect" title="Locally decodable">locally decodable</a> code, which provides a way to recover parts of the original message with high probability, while only looking at a small fraction of the received word. This gives rise to applications in <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> and particularly in the design of <a href="Probabilistically_checkable_proofs" class="mw-redirect" title="Probabilistically checkable proofs">probabilistically checkable proofs</a>.

Since the relative distance of the Hadamard code is 1/2, normally one can only hope to recover from at most a 1/4 fraction of error. Using <a href="List_decoding" title="List decoding">list decoding</a>, however, it is possible to compute a short list of possible candidate messages as long as fewer than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}-\epsilon }">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}-\epsilon }</annotation>

</semantics>

</math><img src="./71398a2265251382260efd680e290da25dd2cdd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.783ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}-\epsilon }" loading="lazy"> of the bits in the received word have been corrupted.

In <a href="Code-division_multiple_access" title="Code-division multiple access">code-division multiple access</a> (CDMA) communication, the Hadamard code is referred to as Walsh Code, and is used to define individual <a href="Communication_channel" title="Communication channel">communication channels</a>. It is usual in the CDMA literature to refer to codewords as “codes”. Each user will use a different codeword, or “code”, to modulate their signal. Because Walsh codewords are mathematically <a href="Orthogonal" class="mw-redirect" title="Orthogonal">orthogonal</a>, a Walsh-encoded signal appears as <a href="Random_noise" class="mw-redirect" title="Random noise">random noise</a> to a CDMA capable mobile <a href="Terminal_(telecommunication)" title="Terminal (telecommunication)">terminal</a>, unless that terminal uses the same codeword as the one used to encode the incoming <a href="Signal_(information_theory)" class="mw-redirect" title="Signal (information theory)">signal</a>.<a href="#cite_note-Langton_2002-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Hadamard code is the name that is most commonly used for this code in the literature. However, in modern use these error correcting codes are referred to as Walsh–Hadamard codes.

There is a reason for this:

<a href="Jacques_Hadamard" title="Jacques Hadamard">Jacques Hadamard</a> did not invent the code himself, but he defined <a href="Hadamard_matrix" title="Hadamard matrix">Hadamard matrices</a> around 1893, long before the first <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting code</a>, the <a href="Hamming_code" title="Hamming code">Hamming code</a>, was developed in the 1940s.

The Hadamard code is based on Hadamard matrices, and while there are many different Hadamard matrices that could be used here, normally only <a href="Hadamard_matrix#Sylvester's_construction" title="Hadamard matrix">Sylvester's construction of Hadamard matrices</a> is used to obtain the codewords of the Hadamard code.

<a href="James_Joseph_Sylvester" title="James Joseph Sylvester">James Joseph Sylvester</a> developed his construction of Hadamard matrices in 1867, which actually predates Hadamard's work on Hadamard matrices. Hence the name Hadamard code is disputed and sometimes the code is called Walsh code, honoring the American mathematician <a href="Joseph_Leonard_Walsh" class="mw-redirect" title="Joseph Leonard Walsh">Joseph Leonard Walsh</a>.

An augmented Hadamard code was used during the 1971 <a href="Mariner_9" title="Mariner 9">Mariner 9</a> mission to correct for picture transmission errors. The binary values used during this mission were 6 bits long, which represented 64 <a href="Grayscale" title="Grayscale">grayscale</a> values.

Because of limitations of the quality of the alignment of the transmitter at the time (due to Doppler Tracking Loop issues) the maximum useful data length was about 30 bits. Instead of using a <a href="Repetition_code" title="Repetition code">repetition code</a>, a [32, 6, 16] Hadamard code was used.

Errors of up to 7 bits per 32-bit word could be corrected using this scheme. Compared to a 5-<a href="Repetition_code" title="Repetition code">repetition code</a>, the error correcting properties of this Hadamard code are much better, yet its rate is comparable. The efficient decoding algorithm was an important factor in the decision to use this code.

The circuitry used was called the "Green Machine". It employed the <a href="Fast_Fourier_transform" title="Fast Fourier transform">fast Fourier transform</a> which can increase the decoding speed by a factor of three. Since the 1990s use of this code by space programs has more or less ceased, and the <a href="NASA_Deep_Space_Network" title="NASA Deep Space Network">NASA Deep Space Network</a> does not support this error correction scheme for its dishes that are greater than 26 m.

<div class="mw-heading mw-heading2"><h2 id="Constructions">Constructions</h2></div>

While all Hadamard codes are based on Hadamard matrices, the constructions differ in subtle ways for different scientific fields, authors, and uses. Engineers, who use the codes for data transmission, and <a href="Coding_theory" title="Coding theory">coding theorists</a>, who analyse extremal properties of codes, typically want the <a href="Block_code#The_rate_R" title="Block code">rate</a> of the code to be as high as possible, even if this means that the construction becomes mathematically slightly less elegant.

On the other hand, for many applications of Hadamard codes in <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> it is not so important to achieve the optimal rate, and hence simpler constructions of Hadamard codes are preferred since they can be analyzed more elegantly.

<div class="mw-heading mw-heading3"><h3 id="Construction_using_inner_products">Construction using inner products</h3></div>

When given a binary message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./4535992aa6b5e1b799665d67ffd780cecc03b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.176ex;" alt="{\displaystyle x\in \{0,1\}^{k}}" loading="lazy"> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, the Hadamard code encodes the message into a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Had}}(x)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}(x)}</annotation>

</semantics>

</math><img src="./a54c2d5d678522c4e2d44bd747f5bfad93b7a779.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.337ex; height:2.843ex;" alt="{\displaystyle {\text{Had}}(x)}" loading="lazy"> using an encoding function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}</annotation>

</semantics>

</math><img src="./1c093bb8d76aeddb5a42f62463d2b988dd78ac01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.766ex; height:3.509ex;" alt="{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}" loading="lazy">

This function makes use of the <a href="Inner_product" class="mw-redirect" title="Inner product">inner product</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle x,y\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle x,y\rangle }</annotation>

</semantics>

</math><img src="./9df1806ebe1fed1a728b18aed82c30be8b2a0acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle \langle x,y\rangle }" loading="lazy"> of two vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./043206429e3cc21369ae4effc8c3207ca49df9ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.132ex; height:3.176ex;" alt="{\displaystyle x,y\in \{0,1\}^{k}}" loading="lazy">, which is defined as follows:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}</annotation>

</semantics>

</math><img src="./c224532968975fc4a496b4d43c6f970ec6a83047.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:25.276ex; height:7.343ex;" alt="{\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}" loading="lazy"></dd></dl>

Then the Hadamard encoding of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is defined as the sequence of all inner products with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">:

</mrow>

</mrow>

<msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}</annotation>

</semantics>

</math><img src="./d6319d3bd02bf148d21cd0765875cdf4e87aaa63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:25.29ex; height:5.343ex;" alt="{\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}" loading="lazy"></dd></dl>

As mentioned above, the augmented Hadamard code is used in practice since the Hadamard code itself is somewhat wasteful.

This is because, if the first bit of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is zero, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}=0}</annotation>

</semantics>

</math><img src="./0ff2cde62f4affa983601a506f2740aaa0d808d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.454ex; height:2.509ex;" alt="{\displaystyle y_{1}=0}" loading="lazy">, then the inner product contains no information whatsoever about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy">, and hence, it is impossible to fully decode <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> from those positions of the codeword alone.

On the other hand, when the codeword is restricted to the positions where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}=1}</annotation>

</semantics>

</math><img src="./4d3a3092e1bc438029617f570a55c7de73352205.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.454ex; height:2.509ex;" alt="{\displaystyle y_{1}=1}" loading="lazy">, it is still possible to fully decode <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.

Hence it makes sense to restrict the Hadamard code to these positions, which gives rise to the augmented Hadamard encoding of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">; that is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}">

</mrow>

</mrow>

<msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}</annotation>

</semantics>

</math><img src="./6df22572f7bb1ad54a36b13f55ae48d63832c9be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:32.032ex; height:5.343ex;" alt="{\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Construction_using_a_generator_matrix">Construction using a generator matrix</h3></div>

The Hadamard code is a linear code, and all linear codes can be generated by a <a href="Generator_matrix" title="Generator matrix">generator matrix</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">. This is a matrix such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Had}}(x)=x\cdot G}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}(x)=x\cdot G}</annotation>

</semantics>

</math><img src="./4db00c2483e3cb82ef7b274035aeef9cbecaebd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.271ex; height:2.843ex;" alt="{\displaystyle {\text{Had}}(x)=x\cdot G}" loading="lazy"> holds for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./4535992aa6b5e1b799665d67ffd780cecc03b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.176ex;" alt="{\displaystyle x\in \{0,1\}^{k}}" loading="lazy">, where the message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is viewed as a row vector and the vector-matrix product is understood in the <a href="Vector_space" title="Vector space">vector space</a> over the <a href="Finite_field" title="Finite field">finite field</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}}</annotation>

</semantics>

</math><img src="./fde97f1e971e76227cd0aac645b7b0901d7b668d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle \mathbb {F} _{2}}" loading="lazy">. In particular, an equivalent way to write the inner product definition for the Hadamard code arises by using the generator matrix whose columns consist of all strings <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, that is,

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}</annotation>

</semantics>

</math><img src="./fa7c17a9ec5dfe88553e8332f6cfd42876028db9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:27.908ex; height:9.509ex;" alt="{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}\in \{0,1\}^{k}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./1813c373c17f428f920f40064f59f27f22b4804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.552ex; height:3.176ex;" alt="{\displaystyle y_{i}\in \{0,1\}^{k}}" loading="lazy"> is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th binary vector in <a href="Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical order</a>.

For example, the generator matrix for the Hadamard code of dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=3}</annotation>

</semantics>

</math><img src="./662e06a2436f8a44fec791f5c794621f10dc8f30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=3}" loading="lazy"> is:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}.}</annotation>

</semantics>

</math><img src="./8b1f24dd029c73fae9c9ad0452c597a91837ea74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:34.982ex; height:9.176ex;" alt="{\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}.}" loading="lazy"></dd></dl>

The matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k\times 2^{k})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (k\times 2^{k})}</annotation>

</semantics>

</math><img src="./35084864095d76ca5c640d16104ee212eee3206b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.112ex; height:3.176ex;" alt="{\displaystyle (k\times 2^{k})}" loading="lazy">-matrix and gives rise to the <a href="Linear_operator" class="mw-redirect" title="Linear operator">linear operator</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}</annotation>

</semantics>

</math><img src="./fb90b84c967fc15d6517a4c0710f5b9700adc822.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.119ex; height:3.509ex;" alt="{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}" loading="lazy">.

The generator matrix of the augmented Hadamard code is obtained by restricting the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> to the columns whose first entry is one.

For example, the generator matrix for the augmented Hadamard code of dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=3}</annotation>

</semantics>

</math><img src="./662e06a2436f8a44fec791f5c794621f10dc8f30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=3}" loading="lazy"> is:

<msup>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}</annotation>

</semantics>

</math><img src="./e0f814f6cafcf80ab88f48c71f6aa7dc7168f48a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:21.726ex; height:9.176ex;" alt="{\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}" loading="lazy"></dd></dl>

Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}</annotation>

</semantics>

</math><img src="./b58070ae468991be6ac3c799e3132bde822b57aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.117ex; height:3.509ex;" alt="{\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}" loading="lazy"> is a linear mapping with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{pHad}}(x)=x\cdot G'}">

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{pHad}}(x)=x\cdot G'}</annotation>

</semantics>

</math><img src="./03dcf7d36e6fbd730bba7c1a42241dc28dd1d690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.248ex; height:3.009ex;" alt="{\displaystyle {\text{pHad}}(x)=x\cdot G'}" loading="lazy">.

For general <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, the generator matrix of the augmented Hadamard code is a <a href="Parity-check_matrix" title="Parity-check matrix">parity-check matrix</a> for the <a href="Hamming_code#Hamming_codes_with_additional_parity_(SECDED)" title="Hamming code">extended Hamming code</a> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}}</annotation>

</semantics>

</math><img src="./ddfa44836396d742f76f25213117e820c4584d2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.352ex; height:2.676ex;" alt="{\displaystyle 2^{k-1}}" loading="lazy"> and dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}-k}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}-k}</annotation>

</semantics>

</math><img src="./9e6c220e7e539e8a76a2148434f06dff20a89513.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.403ex; height:2.843ex;" alt="{\displaystyle 2^{k-1}-k}" loading="lazy">, which makes the augmented Hadamard code the <a href="Dual_code" title="Dual code">dual code</a> of the extended Hamming code.

Hence an alternative way to define the Hadamard code is in terms of its parity-check matrix: the parity-check matrix of the Hadamard code is equal to the generator matrix of the Hamming code.

<div class="mw-heading mw-heading3"><h3 id="Construction_using_general_Hadamard_matrices">Construction using general Hadamard matrices</h3></div>

Hadamard codes are obtained from an n-by-n <a href="Hadamard_matrix" title="Hadamard matrix">Hadamard matrix</a> H. In particular, the 2n codewords of the code are the rows of H and the rows of −H. To obtain a code over the alphabet {0,1}, the mapping −1 ↦ 1, 1 ↦ 0, or, equivalently, x ↦ (1 − x)/2, is applied to the matrix elements. That the minimum distance of the code is n/2 follows from the defining property of Hadamard matrices, namely that their rows are mutually orthogonal. This implies that two distinct rows of a Hadamard matrix differ in exactly n/2 positions, and, since negation of a row does not affect orthogonality, that any row of H differs from any row of −H in n/2 positions as well, except when the rows correspond, in which case they differ in n positions.

To get the augmented Hadamard code above with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k-1}}</annotation>

</semantics>

</math><img src="./f4b460a6fe1b4da0a15c0d2403e974d6541efaf9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.845ex; height:2.676ex;" alt="{\displaystyle n=2^{k-1}}" loading="lazy">, the chosen Hadamard matrix H has to be of Sylvester type, which gives rise to a message length of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(2n)=k}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(2n)=k}</annotation>

</semantics>

</math><img src="./7014dbe489763ffc574ed3870fe91bcca83a27ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.702ex; height:2.843ex;" alt="{\displaystyle \log _{2}(2n)=k}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Distance">Distance</h2></div>

The distance of a code is the minimum <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> between any two distinct codewords, i.e., the minimum number of positions at which two distinct codewords differ. Since the Walsh–Hadamard code is a <a href="Linear_code" title="Linear code">linear code</a>, the distance is equal to the minimum <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> among all of its non-zero codewords. All non-zero codewords of the Walsh–Hadamard code have a <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> of exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}}</annotation>

</semantics>

</math><img src="./ddfa44836396d742f76f25213117e820c4584d2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.352ex; height:2.676ex;" alt="{\displaystyle 2^{k-1}}" loading="lazy"> by the following argument.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./4535992aa6b5e1b799665d67ffd780cecc03b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.176ex;" alt="{\displaystyle x\in \{0,1\}^{k}}" loading="lazy"> be a non-zero message. Then the following value is exactly equal to the fraction of positions in the codeword that are equal to one:

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr _{y\in \{0,1\}^{k}}{\big [}({\text{Had}}(x))_{y}=1{\big ]}=\Pr _{y\in \{0,1\}^{k}}{\big [}\langle x,y\rangle =1{\big ]}\,.}</annotation>

</semantics>

</math><img src="./06608d6f4e85e02437feadfee966819b06cefd0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:45.868ex; height:5.176ex;" alt="{\displaystyle \Pr _{y\in \{0,1\}^{k}}{\big [}({\text{Had}}(x))_{y}=1{\big ]}=\Pr _{y\in \{0,1\}^{k}}{\big [}\langle x,y\rangle =1{\big ]}\,.}" loading="lazy"></dd></dl>

The fact that the latter value is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy"> is called the random subsum principle. To see that it is true, assume without loss of generality that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}=1}</annotation>

</semantics>

</math><img src="./68209597f05acea5c148021527eb7fe21bd77a55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.645ex; height:2.509ex;" alt="{\displaystyle x_{1}=1}" loading="lazy">.

Then, when conditioned on the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{2},\dots ,y_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{2},\dots ,y_{k}}</annotation>

</semantics>

</math><img src="./354720f91e61968b5c2b90a800f34f4452bbe1dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.6ex; height:2.009ex;" alt="{\displaystyle y_{2},\dots ,y_{k}}" loading="lazy">, the event is equivalent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}\cdot x_{1}=b}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}\cdot x_{1}=b}</annotation>

</semantics>

</math><img src="./138657f8beb8d7c0d76f57280e9f5a5999c7200c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.353ex; height:2.509ex;" alt="{\displaystyle y_{1}\cdot x_{1}=b}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in \{0,1\}}</annotation>

</semantics>

</math><img src="./b250aa33a7d342ab8b242e87ec4690bd0b5b8dd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.522ex; height:2.843ex;" alt="{\displaystyle b\in \{0,1\}}" loading="lazy"> depending on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2},\dots ,x_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2},\dots ,x_{k}}</annotation>

</semantics>

</math><img src="./e31fab4eb78e407fa7175f9a9ae126a55a702961.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.981ex; height:2.009ex;" alt="{\displaystyle x_{2},\dots ,x_{k}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{2},\dots ,y_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{2},\dots ,y_{k}}</annotation>

</semantics>

</math><img src="./354720f91e61968b5c2b90a800f34f4452bbe1dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.6ex; height:2.009ex;" alt="{\displaystyle y_{2},\dots ,y_{k}}" loading="lazy">. The probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}=b}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}=b}</annotation>

</semantics>

</math><img src="./0816bd872d011ec74e849cea875c0a3aeb511658.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.289ex; height:2.509ex;" alt="{\displaystyle y_{1}=b}" loading="lazy"> happens is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">. Thus, in fact, all non-zero codewords of the Hadamard code have relative Hamming weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">, and thus, its relative distance is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">.

The relative distance of the augmented Hadamard code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy"> as well, but it no longer has the property that every non-zero codeword has weight exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy"> since the all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">s vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{2^{k-1}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{2^{k-1}}}</annotation>

</semantics>

</math><img src="./cb2271496c19e8486fbf770c15ab75d8c30cd909.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.782ex; height:3.009ex;" alt="{\displaystyle 1^{2^{k-1}}}" loading="lazy"> is a codeword of the augmented Hadamard code. This is because the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=10^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=10^{k-1}}</annotation>

</semantics>

</math><img src="./3d93cc6b4fd2b685db58a636237f88dae587b9e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.942ex; height:2.676ex;" alt="{\displaystyle x=10^{k-1}}" loading="lazy"> encodes to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}</annotation>

</semantics>

</math><img src="./a4cac35c4063c3372ee5462e234c8a94668da68b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.694ex; height:3.509ex;" alt="{\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}" loading="lazy">. Furthermore, whenever <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is non-zero and not the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10^{k-1}}</annotation>

</semantics>

</math><img src="./901bd2d4718add7826cb5510eb592de0c62edd27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.514ex; height:2.676ex;" alt="{\displaystyle 10^{k-1}}" loading="lazy">, the random subsum principle applies again, and the relative weight of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Had}}(x)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Had}}(x)}</annotation>

</semantics>

</math><img src="./a54c2d5d678522c4e2d44bd747f5bfad93b7a779.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.337ex; height:2.843ex;" alt="{\displaystyle {\text{Had}}(x)}" loading="lazy"> is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Local_decodability">Local decodability</h2></div>

A <a href="Locally_decodable" class="mw-redirect" title="Locally decodable">locally decodable</a> code is a code that allows a single bit of the original message to be recovered with high probability by only looking at a small portion of the received word.

A code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">-query <a href="Locally_decodable" class="mw-redirect" title="Locally decodable">locally decodable</a> if a message bit, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy">, can be recovered by checking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> bits of the received word. More formally, a code, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./ac987756d8f3cf1659b6825f3d3f6729896dbeec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.992ex; height:3.176ex;" alt="{\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}" loading="lazy">, is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}</annotation>

</semantics>

</math><img src="./4edb031d2c0b8dce7efce0a93d54533fe12457e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.461ex; height:2.843ex;" alt="{\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}" loading="lazy">-locally decodable, if there exists a probabilistic decoder, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./6c312cbaa6900da0d084ae7c0beca272c0645a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.15ex; height:3.176ex;" alt="{\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}" loading="lazy">, such that (Note: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (x,y)}</annotation>

</semantics>

</math><img src="./6224a4de5239044c9a9eacc93a6363beddf3687d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.264ex; height:2.843ex;" alt="{\displaystyle \Delta (x,y)}" loading="lazy"> represents the <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> between vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">):

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./5d724646ae8b8cc7b980821e70511b675fb759f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.46ex; height:3.176ex;" alt="{\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (y,C(x))\leq \delta n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (y,C(x))\leq \delta n}</annotation>

</semantics>

</math><img src="./f446372ffb0170a56b1af10abaaa82b8272ef511.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.382ex; height:2.843ex;" alt="{\displaystyle \Delta (y,C(x))\leq \delta n}" loading="lazy"> implies that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}</annotation>

</semantics>

</math><img src="./e32fc2f85a3ba5f7a3583457ef5ebf38830a2d00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:32.36ex; height:5.176ex;" alt="{\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}" loading="lazy">

Theorem 1: The Walsh–Hadamard code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}</annotation>

</semantics>

</math><img src="./9db638faea462e59d5d07612c23ee4a88181cf5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.138ex; height:5.176ex;" alt="{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}" loading="lazy">-locally decodable for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}</annotation>

</semantics>

</math><img src="./b91ff6584512a43f257f4fdc73d5e1608dc1dac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.407ex; height:5.176ex;" alt="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}" loading="lazy">.

Lemma 1: For all codewords, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> in a Walsh–Hadamard code, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}+c_{j}=c_{i+j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}+c_{j}=c_{i+j}}</annotation>

</semantics>

</math><img src="./ff507d1b8854ec56334af7d4516ec3430f4795a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.424ex; height:2.676ex;" alt="{\displaystyle c_{i}+c_{j}=c_{i+j}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i},c_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i},c_{j}}</annotation>

</semantics>

</math><img src="./44050b7828a74f7289d3f001af8d65feb3a2cbe5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.757ex; height:2.343ex;" alt="{\displaystyle c_{i},c_{j}}" loading="lazy"> represent the bits in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> in positions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> respectively, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i+j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i+j}}</annotation>

</semantics>

</math><img src="./ca80541cc0a8ec4ed02bf52f752523535457ecf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.763ex; height:2.343ex;" alt="{\displaystyle c_{i+j}}" loading="lazy"> represents the bit at position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+j)}</annotation>

</semantics>

</math><img src="./710a0126617ce2001458ebedf0bfae40e124c227.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.41ex; height:2.843ex;" alt="{\displaystyle (i+j)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Proof_of_lemma_1">Proof of lemma 1</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}">

<msub>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}</annotation>

</semantics>

</math><img src="./ffb7ad539c29bea69421cef86699d6f4e4548b4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.284ex; height:2.843ex;" alt="{\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}" loading="lazy"> be the codeword in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> corresponding to message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}</annotation>

</semantics>

</math><img src="./7577ac78adb2ba45d21e26cef76f36e7b1a15b98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:28.99ex; height:9.509ex;" alt="{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}" loading="lazy"> be the generator matrix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">.

By definition, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}=x\cdot g_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}=x\cdot g_{i}}</annotation>

</semantics>

</math><img src="./cfb5d06082b39610d9923c8e25dd6be07517c1d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.822ex; height:2.009ex;" alt="{\displaystyle c_{i}=x\cdot g_{i}}" loading="lazy">. From this, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}</annotation>

</semantics>

</math><img src="./436f44509622b0865f9b56442769161e9e4d58a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:37.132ex; height:3.009ex;" alt="{\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}" loading="lazy">. By the construction of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}+g_{j}=g_{i+j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}+g_{j}=g_{i+j}}</annotation>

</semantics>

</math><img src="./2e3781f28dde5f9cb9c29a7fd2a0fe223c969a0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.731ex; height:2.676ex;" alt="{\displaystyle g_{i}+g_{j}=g_{i+j}}" loading="lazy">. Therefore, by substitution, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}</annotation>

</semantics>

</math><img src="./c77145e7345f15450caa5b7eabb5af31094ef57f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.396ex; height:2.676ex;" alt="{\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Proof_of_theorem_1">Proof of theorem 1</h3></div>

To prove theorem 1 we will construct a decoding algorithm and prove its correctness.

<div class="mw-heading mw-heading4"><h4 id="Algorithm">Algorithm</h4></div>

Input: Received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}">

<msub>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}</annotation>

</semantics>

</math><img src="./05014480cb625f828de1f923f2ae122a345fb832.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.694ex; height:2.843ex;" alt="{\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}" loading="lazy">

For each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in \{1,\dots ,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in \{1,\dots ,n\}}</annotation>

</semantics>

</math><img src="./55cb337f87f66a675fe0c7c3d4ecaa801f989a47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.703ex; height:2.843ex;" alt="{\displaystyle i\in \{1,\dots ,n\}}" loading="lazy">:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\in \{0,\dots ,2^{n}-1\}}</annotation>

</semantics>

</math><img src="./b4e0b75207e5de0b5a39b3d3e68b0655b84e9bb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:18.875ex; height:2.843ex;" alt="{\displaystyle j\in \{0,\dots ,2^{n}-1\}}" loading="lazy"> uniformly at random.</li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \{0,\dots ,2^{n}-1\}}</annotation>

</semantics>

</math><img src="./b254f54526cded5189324bccad19560465af455c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.101ex; height:2.843ex;" alt="{\displaystyle k\in \{0,\dots ,2^{n}-1\}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j+k=e_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j+k=e_{i}}</annotation>

</semantics>

</math><img src="./9b8672043f7ce55bf4cd9bc18421fdc1217b1fb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:10.018ex; height:2.509ex;" alt="{\displaystyle j+k=e_{i}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{i}}</annotation>

</semantics>

</math><img src="./ebdc3a9cb1583d3204eff8918b558c293e0d2cf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.883ex; height:2.009ex;" alt="{\displaystyle e_{i}}" loading="lazy"> is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th <a href="Standard_basis" title="Standard basis">standard basis vector</a> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j+k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j+k}</annotation>

</semantics>

</math><img src="./3c24eabd6255c2af4b889c4fa863fd3ff9619d55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:5.036ex; height:2.509ex;" alt="{\displaystyle j+k}" loading="lazy"> is the bitwise xor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">.</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\gets y_{j}+y_{k}}</annotation>

</semantics>

</math><img src="./d100124b4fad79bb27df1fc5725693ac16fc2df3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.861ex; height:2.676ex;" alt="{\displaystyle x_{i}\gets y_{j}+y_{k}}" loading="lazy">.</li></ol>

Output: Message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=(x_{1},\dots ,x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=(x_{1},\dots ,x_{n})}</annotation>

</semantics>

</math><img src="./4328c0b5216791ddb0b9aea9cf7d5f460e6481c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.348ex; height:2.843ex;" alt="{\displaystyle x=(x_{1},\dots ,x_{n})}" loading="lazy">

<div class="mw-heading mw-heading4"><h4 id="Proof_of_correctness">Proof of correctness</h4></div>

For any message, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, and received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> differs from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=C(x)}</annotation>

</semantics>

</math><img src="./6be9fe9cc5a47c9b7c6c5ace83be920c0e4c6e12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.011ex; height:2.843ex;" alt="{\displaystyle c=C(x)}" loading="lazy"> on at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> fraction of bits, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> can be decoded with probability at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}">

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}</annotation>

</semantics>

</math><img src="./66ea23556c03166fc59d56f6bddf6af69dbf391e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.698ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}" loading="lazy">.

By lemma 1, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}</annotation>

</semantics>

</math><img src="./23e152cd345a518ac0af762abf7b0ae85f9fd247.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:37.482ex; height:2.676ex;" alt="{\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> are picked uniformly, the probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}\not =c_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\not =c_{j}}</annotation>

</semantics>

</math><img src="./8e107e54732e514db49ded525ec9e50771f19f4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.064ex; height:2.843ex;" alt="{\displaystyle y_{j}\not =c_{j}}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy">. Similarly, the probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}\not =c_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}\not =c_{k}}</annotation>

</semantics>

</math><img src="./537b758b3f6e0a0eb19f0d55da63f71de82c225f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.422ex; height:2.676ex;" alt="{\displaystyle y_{k}\not =c_{k}}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy">. By the <a href="Union_bound" class="mw-redirect" title="Union bound">union bound</a>, the probability that either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}}</annotation>

</semantics>

</math><img src="./f8df4e372390588acb968986cfc388e50b930b3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.049ex; height:2.343ex;" alt="{\displaystyle y_{j}}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}}</annotation>

</semantics>

</math><img src="./4b2ab0248723a410cc2c67ce06ad5c043dcbb933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.009ex;" alt="{\displaystyle y_{k}}" loading="lazy"> do not match the corresponding bits in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\delta }</annotation>

</semantics>

</math><img src="./1eb07ea6b418948bdfb59fcfd066dec83d281f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.211ex; height:2.343ex;" alt="{\displaystyle 2\delta }" loading="lazy">. If both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}}</annotation>

</semantics>

</math><img src="./f8df4e372390588acb968986cfc388e50b930b3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.049ex; height:2.343ex;" alt="{\displaystyle y_{j}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}}</annotation>

</semantics>

</math><img src="./4b2ab0248723a410cc2c67ce06ad5c043dcbb933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.009ex;" alt="{\displaystyle y_{k}}" loading="lazy"> correspond to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">, then lemma 1 will apply, and therefore, the proper value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> will be computed. Therefore, the probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is decoded properly is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-2\delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-2\delta }</annotation>

</semantics>

</math><img src="./48ee8fe498973c6e1a8dfc33affc5d2040766343.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.214ex; height:2.509ex;" alt="{\displaystyle 1-2\delta }" loading="lazy">. Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon ={\frac {1}{2}}-2\delta }">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon ={\frac {1}{2}}-2\delta }</annotation>

</semantics>

</math><img src="./56765aee091ccfbf607bb7b67f00e2c856ec09a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:11.093ex; height:5.176ex;" alt="{\displaystyle \epsilon ={\frac {1}{2}}-2\delta }" loading="lazy"> and for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"> to be positive, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}</annotation>

</semantics>

</math><img src="./b91ff6584512a43f257f4fdc73d5e1608dc1dac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.407ex; height:5.176ex;" alt="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}" loading="lazy">.

Therefore, the Walsh–Hadamard code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}</annotation>

</semantics>

</math><img src="./9db638faea462e59d5d07612c23ee4a88181cf5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.138ex; height:5.176ex;" alt="{\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}" loading="lazy"> locally decodable for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}</annotation>

</semantics>

</math><img src="./b91ff6584512a43f257f4fdc73d5e1608dc1dac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.407ex; height:5.176ex;" alt="{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Optimality">Optimality</h2></div>

For k ≤ 7 the linear Hadamard codes have been proven optimal in the sense of minimum distance.<a href="#cite_note-Jaffe-Bouyukliev_2007-7">[7]</a>

<ul><li><a href="Zadoff%E2%80%93Chu_sequence" title="Zadoff–Chu sequence">Zadoff–Chu sequence</a> — improve over the Walsh–Hadamard codes</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMalek2006" class="citation book cs1">Malek, Massoud (2006). "Hadamard Codes". <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200109044013/http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf">Coding Theory</a> (PDF). Archived from <a rel="nofollow" class="external text" href="http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf">the original</a> (PDF) on 2020-01-09.</cite>

</li>

<li id="cite_note-Amadei-Manzoli-Merani_2002-2"><a href="#cite_ref-Amadei-Manzoli-Merani_2002_2-0">^</a> <cite id="CITEREFAmadeiManzoliMerani2002" class="citation book cs1">Amadei, M.; Manzoli, Umberto; Merani, Maria Luisa (2002-11-17). "On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users". Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE. Vol. 1. <a href="IEEE" class="mw-redirect" title="IEEE">IEEE</a>. pp. 841–845. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FGLOCOM.2002.1188196">10.1109/GLOCOM.2002.1188196</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7803-7632-3</bdi>.</cite>

</li>

<li id="cite_note-Arora-Barak_2009-3"><a href="#cite_ref-Arora-Barak_2009_3-0">^</a> <cite id="CITEREFAroraBarak2009" class="citation book cs1"><a href="Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a>; Barak, Boaz (2009). "Section 19.2.2". <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/theory/complexity/">Computational Complexity: A Modern Approach</a>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-42426-4</bdi>.</cite>

</li>

<li id="cite_note-Guruswami_2009-4"><a href="#cite_ref-Guruswami_2009_4-0">^</a> <cite id="CITEREFGuruswami2009" class="citation book cs1">Guruswami, Venkatesan (2009). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~venkatg/pubs/papers/ld-binary-ms.pdf">List decoding of binary codes</a> (PDF). p. 3.</cite>

</li>

<li id="cite_note-Bose-Shrikhande_1959-5"><a href="#cite_ref-Bose-Shrikhande_1959_5-0">^</a> <cite id="CITEREFBoseShrikhande1959" class="citation journal cs1"><a href="Raj_Chandra_Bose" title="Raj Chandra Bose">Bose, Raj Chandra</a>; <a href="Sharadchandra_Shankar_Shrikhande" title="Sharadchandra Shankar Shrikhande">Shrikhande, Sharadchandra Shankar</a> (June 1959). "A note on a result in the theory of code construction". <a href="Information_and_Control" class="mw-redirect" title="Information and Control">Information and Control</a>. 2 (2): 183–194. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.2879">10.1.1.154.2879</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2859%2990376-6">10.1016/S0019-9958(59)90376-6</a>.</cite>

</li>

<li id="cite_note-Langton_2002-6"><a href="#cite_ref-Langton_2002_6-0">^</a> <cite id="CITEREFLangton2002" class="citation web cs1 cs1-prop-interproj-linked-name"><a href="https://www.wikidata.org/wiki/Q61476932" class="extiw external" title="d:Q61476932">Langton, Charan</a> [at Wikidata] (2002). <a rel="nofollow" class="external text" href="http://complextoreal.com/wp-content/uploads/2013/01/CDMA.pdf">"CDMA Tutorial: Intuitive Guide to Principles of Communications"</a> (PDF). Complex to Real. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110720084646/http://www.complextoreal.com/CDMA.pdf">Archived</a> (PDF) from the original on 2011-07-20. Retrieved 2017-11-10.</cite>

</li>

<li id="cite_note-Jaffe-Bouyukliev_2007-7"><a href="#cite_ref-Jaffe-Bouyukliev_2007_7-0">^</a> <cite id="CITEREFJaffeBouyukliev" class="citation web cs1">Jaffe, David B.; Bouyukliev, Iliya. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070808235329/http://www.math.unl.edu/~djaffe2/papers/sevens.html">"Optimal binary linear codes of dimension at most seven"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.math.unl.edu/~djaffe2/papers/sevens.html">the original</a> on 2007-08-08. Retrieved 2007-08-21.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFRudra" class="citation web cs1">Rudra, Atri. <a rel="nofollow" class="external text" href="http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/lectures/lect4.pdf">"Hamming code and Hamming bound"</a> (PDF). Lecture notes.</cite></li>

<li><cite id="CITEREFRudolphRudolph2011" class="citation book cs1 cs1-prop-foreign-lang-source">Rudolph, Dietmar; Rudolph, Matthias (2011-04-12). "46.4. Hadamard– oder Walsh–Codes". <a rel="nofollow" class="external text" href="http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf">Modulationsverfahren</a> (PDF) (in German). Cottbus, Germany: <a href="Brandenburg_University_of_Technology" title="Brandenburg University of Technology">Brandenburg University of Technology</a> (BTU). p. 214. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210616042506/http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf">Archived</a> (PDF) from the original on 2021-06-16. Retrieved 2021-06-14.</cite> (xiv+225 pages)</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Consultative_Committee_for_Space_Data_Systems222" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Consultative_Committee_for_Space_Data_Systems222" style="font-size:114%;margin:0 4em"><a href="Consultative_Committee_for_Space_Data_Systems" title="Consultative Committee for Space Data Systems">Consultative Committee for Space Data Systems</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data compression</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Images

<li>Data

<ul><li><a href="Adaptive_coding" title="Adaptive coding">Adaptive Entropy Coder</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Error Correction</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<dl><dt>Current</dt>

<dd><a href="Binary_Golay_code" title="Binary Golay code">Binary Golay code</a></dd>

<dd><a href="Concatenated_error_correction_code" title="Concatenated error correction code">Concatenated codes</a></dd>

<dd><a href="Turbo_code" title="Turbo code">Turbo codes</a></dd>

<dt>Proposed</dt>

<dd><a href="Low-density_parity-check_code" title="Low-density parity-check code">LDPC codes</a></dd></dl>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry command uplink</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Command-loss_timer" title="Command-loss timer">Command-loss timer</a></li>

<li><a href="Proximity-1_Space_Link_Protocol" title="Proximity-1 Space Link Protocol">Proximity-1 Space Link Protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry downlink</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Spacecraft_Monitoring_%26_Control" class="mw-redirect" title="Spacecraft Monitoring & Control">Spacecraft Monitoring & Control</a></li>

<li><a href="Beacon_mode_service" title="Beacon mode service">Beacon mode service</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry general</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Space_Communications_Protocol_Specifications" title="Space Communications Protocol Specifications">Space Communications Protocol Specifications</a> (SCPS): <a href="Performance_Enhancing_Proxy" class="mw-redirect" title="Performance Enhancing Proxy">Performance Enhancing Proxy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry modulation systems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<dl><dt>Current</dt>

<dd><a href="OQPSK" class="mw-redirect" title="OQPSK">OQPSK</a></dd>

<dt>Proposed</dt>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Frequencies</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Networking, interoperability and monitoring</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Service-oriented_architecture" title="Service-oriented architecture">Service-oriented architecture</a> (<a href="Message_Abstraction_Layer" title="Message Abstraction Layer">Message Abstraction Layer</a>)</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-17" href="https://en.wikipedia.org/wiki/?title=Hadamard_code&oldid=1290889051">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>